/*
 * @Author: liusheng
 * @Date: 2022-05-02 18:06:06
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-02 21:30:47
 * @Description: 剑指 Offer II 052. 展平二叉搜索树
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 052. 展平二叉搜索树
给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

 

示例 1：



输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：



输入：root = [5,1,7]
输出：[1,null,5,null,7]
 

提示：

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000
 

注意：本题与主站 897 题相同： https://leetcode-cn.com/problems/increasing-order-search-tree/

通过次数14,055 提交次数18,854
 */

#include "header.h"
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        vector<TreeNode *> nodes;
        inorderTraverse(root,nodes);
        int nodeNum = nodes.size();
        if (nodeNum < 1)
        {
            return nullptr;
        }

        TreeNode * newHead = nodes[0];
        TreeNode * preNode = newHead;
        preNode->left = nullptr;
        for (int i = 1; i < nodeNum; ++i)
        {
            TreeNode * curNode = nodes[i];
            curNode->left = nullptr;
            curNode->right = nullptr;
            preNode->right = curNode;

            preNode = curNode;
        }

        return newHead;
    }
private:
    void inorderTraverse(TreeNode * root,vector<TreeNode *> & nodes)
    {
        if (!root)
        {
            return;
        }
        inorderTraverse(root->left,nodes);
        nodes.push_back(root);
        inorderTraverse(root->right,nodes);
    }
};

/* change the node's pointer through inorder traverse */
class Solution2 {
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode * dummyNode = new TreeNode(-1);
        preNode = dummyNode;
        inorderTraverse(root);
        TreeNode * newHead = dummyNode->right;
        delete dummyNode;
        return newHead;
    }
private:
    void inorderTraverse(TreeNode * root)
    {
        if (!root)
        {
            return;
        }

        inorderTraverse(root->left);
        
        preNode->right = root;
        root->left = nullptr;
        preNode = root;

        inorderTraverse(root->right);
    }
private:
    TreeNode * preNode;
};